package LeetCode_SingleLinkedlist;

/**
 * Created with IntelliJ IDEA.
 * Description:将两个升序链表合并成一个非递减链表
 * User: 阿宾
 * Date: 2024-11-06
 * Time: 16:23
 */
public class Demo4 {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode cur1 = list1;
        ListNode cur2 = list2;
        //创建一个新节点，指向新链表的头结点
        ListNode newNode = new ListNode(-1);
        ListNode last = newNode;//last始终指向新链表尾部
        while(cur1 != null && cur2 != null){
            if(cur1.val >= cur2.val){
                last.next = cur2;//连接结点
                //last = cur2;
                cur2 = cur2.next;
            }else{
                last.next = cur1;
                cur1 = cur1.next;
            }
            last = last.next;//更新尾结点
        }
        if(cur1 != null){
            last.next = cur1;
        }
        if(cur2 != null){
            last.next = cur2;
        }
        return newNode.next;
    }

    public static void main(String[] args) {
        // 创建测试链表
        ListNode l1 = new ListNode(1, new ListNode(2,new ListNode(4)));
        ListNode l2 = new ListNode(1,new ListNode(3,new ListNode(4)));
        ListNode result = mergeTwoLists(l1,l2);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }
}
